Search for: All records

We initiate the study of witness authenticating NIZK proof systems (waNIZKs), in which one can use a witness w of a statement x to identify whether a valid proof for x is indeed generated using w. Such a new identification functionality enables more diverse applications, and it also puts new requirements on soundness that: (1) no adversary can generate a valid proof that will not be identified by any witness; (2) or forge a proof using her valid witness to frame others. To work around the obvious obstacle towards conventional zero-knowledgeness, we define entropic zero-knowledgeness that requires the proof to leak no partial information, if the witness has sufficient computational entropy. We give a formal treatment of this new primitive. The modeling turns out to be quite involved and multiple subtle points arise and particular cares are required. We present general constructions from standard assumptions. We also demonstrate three applications in non-malleable (perfectly one-way) hash, group signatures with verifier-local revocations and plaintext-checkable public-key encryption. Our waNIZK provides a new tool to advance the state of the art in all these applications. 

In comparison with conventional content delivery networks, peer-to-peer (p2p) content delivery is promising to save cost and handle high peak-demand, and can also complement the decentralized storage networks such as Filecoin. However, reliable p2p delivery requires proper enforcement of delivery fairness, i.e., the deliverers should be rewarded according to their in-time delivery. Unfortunately, most existing studies on delivery fairness are based on non-cooperative game-theoretic assumptions that are arguably unrealistic in the ad-hoc p2p setting. We for the first time put forth an expressive yet still minimalist security notion for desired fair p2p content delivery, and give two efficient solutions 𝖥𝖺𝗂𝗋𝖣𝗈𝗐𝗇𝗅𝗈𝖺𝖽 and 𝖥𝖺𝗂𝗋𝖲𝗍𝗋𝖾𝖺𝗆 via the blockchain for p2p downloading and p2p streaming scenarios, respectively. Our designs not only guarantee delivery fairness to ensure deliverers be paid (nearly) proportional to their in-time delivery but also ensure the content consumers and content providers are fairly treated. The fairness of each party can be guaranteed when the other two parties collude to arbitrarily misbehave. Moreover, the systems are efficient in the sense of attaining nearly asymptotically optimal on-chain costs and deliverer communication. We implement the protocols and build the prototype systems atop the Ethereum Ropsten network. Extensive experiments done in LAN and WAN settings showcase their high practicality. 

Updatable encryption (UE) is an attractive primitive, which allows the secret key of the outsourced encrypted data to be updated to a fresh one periodically. Several elegant works exist studying various security properties. We notice several major issues in existing security models of (ciphertext dependent) updatable encryption, in particular, integrity and CCA security. The adversary in the models is only allowed to request the server to re-encrypt honestly generated ciphertext, while in practice, an attacker could try to inject arbitrary ciphertexts into the server as she wishes. Those malformed ciphertext could be updated and leveraged by the adversary and cause serious security issues. In this paper, we fill the gap and strengthen the security definitions in multiple aspects: most importantly our integrity and CCA security models remove the restriction in previous models and achieve standard notions of integrity and CCA security in the setting of updatable encryption. Along the way, we refine the security model to capture post-compromise security and enhance the re-encryption indistinguishability to the CCA style. Guided by the new models, we provide a novel construction ReCrypt+, which satisfies our strengthened security definitions. The technical building block of homomorphic hash from a group may be of independent interests. We also study the relations among security notions; and a bit surprisingly, the folklore result in authenticated encryption that IND-CPA plus ciphertext integrity imply IND-CCA security does not hold for ciphertext dependent updatable encryption. 

Recently, Quach, Wee and Wichs (FOCS 2018) proposed a new powerful cryptographic primitive called laconic function evaluation (LFE). Using an LFE scheme, Alice can compress a large circuit f into a small digest. Bob can encrypt some data x under this digest in a way that enables Alice to recover f(x) without learning anything else about Bob’s data. The laconic property requires that the size of the digest, the run-time of the encryption algorithm and the size of the ciphertext should be much smaller than the circuit-size of f. This new tool is motivated by an interesting application of “Bob-optimized” two-round secure two-party computation (2PC). In such a 2PC, Alice will get the final result thus the workload of Bob will be minimized. In this paper, we consider a “client-optimized” two-round secure multiparty computation, in which multiple clients provide inputs and enable a server to obtain final outputs while protecting privacy of each individual input. More importantly, we would also minimize the cost of each client. For this purpose, we propose multi-input laconic function evaluation (MI-LFE), and give a systematic study of it. It turns out that MI-LFE for general circuit is not easy. Specifically, we first show that the directly generalized version, i.e., the public-key MI-LFE implies virtual black-box obfuscation. Hence the public-key MI-LFE (for general circuits) is infeasible. This forces us to turn to secret key version of MI-LFE, in which encryption now needs to take a secret key. Next we show that secret-key MI-LFE also implies heavy cryptographic primitives including witness encryption for NP language and the indistinguishability obfuscation. On the positive side, we show that the secret-key MI-LFE can be constructed assuming indistinguishability obfuscation and learning with errors assumption. Our theoretical results suggest that we may have to explore relaxed versions of MI-LFE for meaningful new applications of “client-optimized” MPC and others.